home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 3 / Info_Mac_1994-01.iso / Development / Source / Bob 1.5 Source / Bobmem.c < prev    next >
Text File  |  1993-10-02  |  15KB  |  623 lines
  1. /* bobmem.c - memory manager */
  2. /*
  3.     Copyright (c) 1991, by David Michael Betz
  4.     All rights reserved
  5. */
  6.  
  7. #include <setjmp.h>
  8. #include "bob.h"
  9.  
  10. /* allocation unit */
  11. typedef char *AUNIT;
  12. #define ALLOCSIZE(x)    (((x) + sizeof(AUNIT) - 1) / sizeof(AUNIT))
  13.  
  14. /* block flags */
  15. #define MARK    1
  16.  
  17. /* size of each type of memory segment */
  18. #define VSSIZE    10000    /* number of LVAL's per vector segment */
  19. #define VCOMPARE(f,s,t)    ((f) + (s) <= (t))
  20.  
  21. /* macros to compute the size of a segment */
  22. #define vsegsize(n) (sizeof(VSEGMENT)+((n)-1)*sizeof(char *))
  23.  
  24. /* macro to convert a byte size to a word size */
  25. #define btow_size(n)    (((n) + sizeof(char *) - 1) / sizeof(char *))
  26.  
  27. /* vector segment structure */
  28. typedef struct vsegment {
  29.     struct vsegment *vs_next;    /* next vector segment */
  30.     AUNIT *vs_free;        /* next free location in this segment */
  31.     AUNIT *vs_top;        /* top of segment (plus one) */
  32.     AUNIT vs_data[1];        /* segment data */
  33. } VSEGMENT;
  34.  
  35. /* global variables */
  36. VALUE symbols;        /* the symbol table */
  37. VALUE classes;        /* the class table */
  38. VALUE stdin_iostream;    /* standard input i/o stream */
  39. VALUE stdout_iostream;    /* standard output i/o stream */
  40. VALUE stderr_iostream;    /* standard error i/o stream */
  41. VALUE nil;        /* the nil value */
  42.  
  43. /* vector (and string) space */
  44. static VSEGMENT *vsegments=NULL;/* list of vector segments */
  45. static VSEGMENT *vscurrent=NULL;/* current vector segment */
  46. static AUNIT *vfree=NULL;    /* next free location in current segment */
  47. static AUNIT *vtop=NULL;    /* top of current segment */
  48.  
  49. /* external variables */
  50. extern jmp_buf error_trap;    /* the error trap target */
  51. extern VECTOR *code;        /* currently executing code vector */
  52.  
  53. /* forward declarations */
  54. #ifdef __STDC__
  55. static DICT_ENTRY *newentry(VALUE *dict,char *key,int type);
  56. static HDR *allocmemory(int type,int size);
  57. static int findvmemory(int size);
  58. static int checkvmemory(int size);
  59. static int makevmemory(int size);
  60. static int vexpand(int size);
  61. static VSEGMENT *newvsegment(unsigned int n);
  62. static void markclass(CLASS *class);
  63. static void markdictionary(DICTIONARY *dict);
  64. static void markentry(DICT_ENTRY *entry);
  65. static void markobject(OBJECT *obj);
  66. static void markvector(VECTOR *vect);
  67. static void compact(void);
  68. static int getblocksize(HDR *hdr);
  69. static void compact_vector(VSEGMENT *vseg);
  70. #else
  71. static HDR *allocmemory();
  72. static void markclass(),markdictionary(),markentry(),markobject();
  73. static void markvector(),compact(),compact_vector();
  74. static DICT_ENTRY *newentry();
  75. #endif
  76.  
  77. /* initialize - initialize the virtual machine */
  78. int initialize(smax)
  79.   int smax;
  80. {
  81.     int obj_class(),cls_new();
  82. /*  char *calloc(); */
  83.     
  84.     /* setup an error trap handler */
  85.     if (setjmp(error_trap) != 0)
  86.     return (FALSE);
  87.  
  88.     /* allocate the stack */
  89.     if ((stkbase = (VALUE *)calloc(1,smax * sizeof(VALUE))) == NULL)
  90.     return (FALSE);
  91.     stktop = sp = stkbase + smax;
  92.     code = NULL;
  93.  
  94.     /* initialize the memory manager */
  95.     vsegments = vscurrent = NULL;
  96.     vfree = vtop = NULL;
  97.  
  98.     /* initialize globals */
  99.     set_nil(&symbols);
  100.     set_nil(&classes);
  101.     set_nil(&stdin_iostream);
  102.     set_nil(&stdout_iostream);
  103.     set_nil(&stderr_iostream);
  104.     set_nil(&nil);
  105.  
  106.     /* create the initial segment */
  107.     if (!vexpand(VSSIZE))
  108.     return (FALSE);
  109.  
  110.     /* create the symbol and class tables */
  111.     set_dictionary(&symbols,newdictionary(&nil));
  112.     set_dictionary(&classes,newdictionary(&nil));
  113.  
  114.     /* enter the built-in functions */
  115.     init_functions();
  116.     return (TRUE);
  117. }
  118.  
  119. /* addentry - add an entry to a dictionary */
  120. DICT_ENTRY *addentry(dict,key,type)
  121.   VALUE *dict; char *key; int type;
  122. {
  123.     DICT_ENTRY *entry;
  124.     if ((entry = findentry(dict,key)) == NULL) {
  125.     check(1);
  126.     push_var(newentry(dict,key,type));
  127.     sp->v.v_var->de_next = *digetcontents(dict);
  128.     dict->v.v_dictionary->di_contents = *sp;
  129.     entry = deaddr(sp++);
  130.     }
  131.     return (entry);
  132. }
  133.  
  134. /* findentry - find an entry in a dictionary */
  135. DICT_ENTRY *findentry(dict,key)
  136.   VALUE *dict; char *key;
  137. {
  138.     DICT_ENTRY *entry;
  139.     int size;
  140.     for (entry = digetcontents(dict)->v.v_var;
  141.      entry != NULL;
  142.      entry = entry->de_next.v.v_var)
  143.     if ((size = strgetsize(&entry->de_key)) == strlen(key)
  144.     &&  strncmp(key,
  145.             strgetdata(&entry->de_key),
  146.             size) == 0)
  147.         return (entry);
  148.     return (NULL);
  149. }
  150.  
  151. /* makestring - make an initialized string from a C-style string */
  152. STRING *makestring(str)
  153.   char *str;
  154. {
  155.     STRING *val;
  156.     int len;
  157.     len = strlen(str);
  158.     val = newstring(len);
  159.     strncpy(val->str_data,str,len);
  160.     return (val);
  161. }
  162.  
  163. /* getcstring - get a C-style version of a string */
  164. char *getcstring(buf,max,str)
  165.   char *buf; int max; VALUE *str;
  166. {
  167.     int len;
  168.     if ((len = strgetsize(str)) >= max)
  169.     len = max - 1;
  170.     strncpy(buf,strgetdata(str),len);
  171.     buf[len] = '\0';
  172.     return (buf);
  173. }
  174.  
  175. /* newstring - allocate a new string object */
  176. STRING *newstring(n)
  177.   int n;
  178. {
  179.     STRING *val;
  180.     int size;
  181.     char *p;
  182.     size = sizeof(STRING) + n - 1;
  183.     val = (STRING *)allocmemory(DT_STRING,size);
  184.     val->str_size = n;
  185.     for (p = val->str_data; --n >= 0; )
  186.     *p++ = '\0';
  187.     return (val);
  188. }
  189.  
  190. /* newobject - allocate a new object */
  191. OBJECT *newobject(class)
  192.   VALUE *class;
  193. {
  194.     OBJECT *val;
  195.     int size,n;
  196.     VALUE *p;
  197.     n = clgetsize(class);
  198.     size = sizeof(OBJECT) + (n - 1) * sizeof(VALUE);
  199.     val = (OBJECT *)allocmemory(DT_OBJECT,size);
  200.     val->obj_class = *class;
  201.     for (p = val->obj_members; --n >= 0; ++p)
  202.     p->v_type = DT_NIL;
  203.     return (val);
  204. }
  205.  
  206. /* newvector - allocate a new vector */
  207. VECTOR *newvector(n)
  208.   int n;
  209. {
  210.     VECTOR *val;
  211.     VALUE *p;
  212.     int size;
  213.     size = sizeof(VECTOR) + (n - 1) * sizeof(VALUE);
  214.     val = (VECTOR *)allocmemory(DT_VECTOR,size);
  215.     val->vec_size = n;
  216.     for (p = val->vec_data; --n >= 0; ++p)
  217.     p->v_type = DT_NIL;
  218.     return (val);
  219. }
  220.  
  221. /* newclass - create a new class */
  222. CLASS *newclass(name,base)
  223.   char *name; VALUE *base;
  224. {
  225.     /* allocate the memory for the new class */
  226.     check(1);
  227.     push_class((CLASS *)allocmemory(DT_CLASS,sizeof(CLASS)));
  228.     set_nil(&sp->v.v_class->cl_name);
  229.     set_nil(&sp->v.v_class->cl_members);
  230.     set_nil(&sp->v.v_class->cl_functions);
  231.  
  232.     /* initialize */
  233.     sp->v.v_class->cl_base = *base;
  234.     set_string(&sp->v.v_class->cl_name,makestring(name));
  235.     set_dictionary(&sp->v.v_class->cl_members,newdictionary(sp));
  236.     set_dictionary(&sp->v.v_class->cl_functions,newdictionary(sp));
  237.     sp->v.v_class->cl_size = 0;
  238.  
  239.     /* return the new class */
  240.     return (claddr(sp++));
  241. }
  242.  
  243. /* newdictionary - create a new dictionary */
  244. DICTIONARY *newdictionary(class)
  245.   VALUE *class;
  246. {
  247.     DICTIONARY *dict;
  248.     dict = (DICTIONARY *)allocmemory(DT_DICTIONARY,sizeof(DICTIONARY));
  249.     dict->di_class = *class;
  250.     set_nil(&dict->di_contents);
  251.     return (dict);
  252. }
  253.  
  254. /* newentry - allocate a new dictionary entry */
  255. static DICT_ENTRY *newentry(dict,key,type)
  256.   VALUE *dict; char *key; int type;
  257. {
  258.     check(1);
  259.     push_var((DICT_ENTRY *)allocmemory(DT_VAR,sizeof(DICT_ENTRY)));
  260.     sp->v.v_var->de_dictionary = *dict;
  261.     sp->v.v_var->de_type = type;
  262.     set_nil(&sp->v.v_var->de_key);
  263.     set_nil(&sp->v.v_var->de_value);
  264.     set_nil(&sp->v.v_var->de_next);
  265.     set_string(&sp->v.v_var->de_key,makestring(key));
  266.     return (deaddr(sp++));
  267. }
  268.  
  269. /* newiostream - create a new i/o stream */
  270. IOSTREAM *newiostream(iod,data)
  271.   IODISPATCH *iod; void *data;
  272. {
  273.     IOSTREAM *ios;
  274.     ios = (IOSTREAM *)allocmemory(DT_IOSTREAM,sizeof(IOSTREAM));
  275.     ios->ios_dispatch = iod;
  276.     ios->ios_data = data;
  277.     return (ios);
  278. }
  279.  
  280. /* allocmemory - allocate a block of memory */
  281. static HDR *allocmemory(type,size)
  282.   int type,size;
  283. {
  284.     HDR *val;
  285.  
  286.     /* make sure there's enough space */
  287.     size = ALLOCSIZE(size);
  288.     if (!VCOMPARE(vfree,size,vtop)
  289.     &&  !checkvmemory(size)
  290.     &&  !findvmemory(size))
  291.     error("Insufficient memory");
  292.  
  293.     /* allocate the next available block */
  294.     val = (HDR *)vfree;
  295.     vfree += size;
  296.     
  297.     /* return the new block of memory */
  298.     val->hdr_type = type;
  299.     val->hdr_flags = 0;
  300.     val->hdr_chain = NULL;
  301.     return (val);
  302. }
  303.  
  304. /* findvmemory - find vector memory */
  305. static int findvmemory(size)
  306.   int size;
  307. {
  308.     /* try garbage collecting */
  309.     gc();
  310.  
  311.     /* check to see if we found enough memory */
  312.     if (VCOMPARE(vfree,size,vtop) || checkvmemory(size))
  313.     return (TRUE);
  314.  
  315.     /* expand vector space */
  316.     return (makevmemory(size));
  317. }
  318.  
  319. /* checkvmemory - check for vector memory (used by 'xsimage.c') */
  320. static int checkvmemory(size)
  321.   int size;
  322. {
  323.     VSEGMENT *vseg;
  324.     for (vseg = vsegments; vseg != NULL; vseg = vseg->vs_next)
  325.     if (vseg != vscurrent && VCOMPARE(vseg->vs_free,size,vseg->vs_top)) {
  326.         if (vscurrent != NULL)
  327.         vscurrent->vs_free = vfree;
  328.         vfree = vseg->vs_free;
  329.         vtop = vseg->vs_top;
  330.         vscurrent = vseg;
  331.         return (TRUE);
  332.     }    
  333.     return (FALSE);
  334. }
  335.     
  336. /* makevmemory - make vector memory (used by 'xsimage.c') */
  337. static int makevmemory(size)
  338.   int size;
  339. {
  340.     return (vexpand(size < VSSIZE ? VSSIZE : size));
  341. }
  342.  
  343. /* vexpand - expand vector space */
  344. static int vexpand(size)
  345.   int size;
  346. {
  347.     VSEGMENT *newvsegment(),*vseg;
  348.  
  349.     /* allocate the new segment */
  350.     if ((vseg = newvsegment(size)) != NULL) {
  351.  
  352.     /* initialize the new segment and make it current */
  353.     if (vscurrent != NULL)
  354.         vscurrent->vs_free = vfree;
  355.     vfree = vseg->vs_free;
  356.     vtop = vseg->vs_top;
  357.     vscurrent = vseg;
  358.     }
  359.     return (vseg != NULL);
  360. }
  361.  
  362. /* newvsegment - create a new vector segment */
  363. static VSEGMENT *newvsegment(n)
  364.   unsigned int n;
  365. {
  366. /*  char *calloc(); */
  367.     VSEGMENT *newseg;
  368.  
  369.     /* allocate the new segment */
  370.     if ((newseg = (VSEGMENT *)calloc(1,vsegsize(n))) == NULL)
  371.     return (NULL);
  372.  
  373.     /* initialize the new segment */
  374.     newseg->vs_free = newseg->vs_data;
  375.     newseg->vs_top = newseg->vs_free + n;
  376.     newseg->vs_next = vsegments;
  377.     vsegments = newseg;
  378.  
  379.     /* return the new segment */
  380.     return (newseg);
  381. }
  382.  
  383. /* gc - garbage collect */
  384. void gc()
  385. {
  386.     extern unsigned char *cbase,*pc;
  387.     VALUE codeval,*p;
  388.     int pcoff;
  389. /*info("GC");*/
  390.  
  391.     /* protect the current bytecode vector */
  392.     if (code) {
  393.     set_bytecode(&codeval,code);
  394.     pcoff = pc - cbase;
  395.     mark(&codeval);
  396.     }
  397.  
  398.     /* mark all reachable values */
  399.     mark(&symbols);
  400.     mark(&classes);
  401.     mark(&stdin_iostream);
  402.     mark(&stdout_iostream);
  403.     mark(&stderr_iostream);
  404.  
  405.     /* mark the stack */
  406.     for (p = sp; p < stktop; )
  407.     mark(p++);
  408.  
  409.     /* mark compiler variables */
  410.     mark_compiler();
  411.  
  412.     /* compact all active blocks */
  413.     compact();
  414.  
  415.     /* reload the interpreter's registers */
  416.     if (code) {
  417.     code = codeval.v.v_vector;
  418.     cbase = code->vec_data[0].v.v_string->str_data;
  419.     pc = cbase + pcoff;
  420.     }
  421. }
  422.  
  423. /* mark - mark all accessible nodes */
  424. void mark(val)
  425.   VALUE *val;
  426. {
  427.     HDR *hdr;
  428.     switch (val->v_type) {
  429.     case DT_CLASS:
  430.     case DT_OBJECT:
  431.     case DT_VECTOR:
  432.     case DT_BYTECODE:
  433.     case DT_STRING:
  434.     case DT_DICTIONARY:
  435.     case DT_VAR:
  436.     case DT_IOSTREAM:
  437.     hdr = val->v.v_hdr;
  438.     val->v.v_chain = hdr->hdr_chain;
  439.     hdr->hdr_chain = val;
  440.     if ((hdr->hdr_flags & MARK) == 0) {
  441.         hdr->hdr_flags |= MARK;
  442.         switch (hdr->hdr_type) {
  443.         case DT_CLASS:
  444.         markclass((CLASS *)hdr);
  445.         break;
  446.         case DT_OBJECT:
  447.         markobject((OBJECT *)hdr);
  448.         break;
  449.         case DT_VECTOR:
  450.         markvector((VECTOR *)hdr);
  451.         break;
  452.         case DT_DICTIONARY:
  453.         markdictionary((DICTIONARY *)hdr);
  454.         break;
  455.         case DT_VAR:
  456.         markentry((DICT_ENTRY *)hdr);
  457.         break;
  458.         }
  459.     }
  460.     break;
  461.     }
  462. }
  463.  
  464. /* markclass - mark a class */
  465. static void markclass(class)
  466.   CLASS *class;
  467. {
  468.     mark(&class->cl_name);
  469.     mark(&class->cl_base);
  470.     mark(&class->cl_members);
  471.     mark(&class->cl_functions);
  472. }
  473.  
  474. /* markdictionary - mark a dictionary */
  475. static void markdictionary(dict)
  476.   DICTIONARY *dict;
  477. {
  478.     VALUE *next,*val;
  479.     mark(&dict->di_class);
  480.     for (val = &dict->di_contents;
  481.      !isnil(val);
  482.      val = next) {
  483.     next = degetnext(val);
  484.     mark(val);
  485.     }
  486. }
  487.  
  488. /* markentry - mark a dictionary entry */
  489. static void markentry(entry)
  490.   DICT_ENTRY *entry;
  491. {
  492.     mark(&entry->de_dictionary);
  493.     mark(&entry->de_key);
  494.     mark(&entry->de_value);
  495. }
  496.  
  497. /* markobject - mark an object */
  498. static void markobject(obj)
  499.   OBJECT *obj;
  500. {
  501.     VALUE *p;
  502.     int n;
  503.     p = obj->obj_members;
  504.     n = clgetsize(&obj->obj_class);
  505.     while (--n >= 0)
  506.     mark(p++);
  507. }
  508.  
  509. /* markvector - mark a vector */
  510. static void markvector(vect)
  511.   VECTOR *vect;
  512. {
  513.     VALUE *p;
  514.     int n;
  515.     p = vect->vec_data;
  516.     n = vect->vec_size;
  517.     while (--n >= 0)
  518.     mark(p++);
  519. }
  520.  
  521. /* compact - compact vector space */
  522. static void compact()
  523. {
  524.     VSEGMENT *vseg;
  525.  
  526.     /* store the current segment information */
  527.     if (vscurrent)
  528.     vscurrent->vs_free = vfree;
  529.  
  530.     /* compact each vector segment */
  531.     for (vseg = vsegments; vseg != NULL; vseg = vseg->vs_next)
  532.     compact_vector(vseg);
  533.  
  534.     /* make the first vector segment current */
  535.     if ((vscurrent = vsegments) != NULL) {
  536.     vfree = vscurrent->vs_free;
  537.     vtop = vscurrent->vs_top;
  538.     }
  539. }
  540.  
  541. /* getblocksize - get the size of a block */
  542. static int getblocksize(hdr)
  543.   HDR *hdr;
  544. {
  545.     switch (hdr->hdr_type) {
  546.     case DT_CLASS:
  547.     return (ALLOCSIZE(sizeof(CLASS)));
  548.     case DT_OBJECT:
  549.     return (ALLOCSIZE(sizeof(OBJECT)
  550.          +  (clgetsize(&((OBJECT *)hdr)->obj_class) - 1) * sizeof(VALUE)));
  551.     case DT_VECTOR:
  552.     return (ALLOCSIZE(sizeof(VECTOR)
  553.          +  (((VECTOR *)hdr)->vec_size - 1) * sizeof(VALUE)));
  554.     case DT_STRING:
  555.     return (ALLOCSIZE(sizeof(STRING)
  556.          +  ((STRING *)hdr)->str_size - 1));
  557.     case DT_DICTIONARY:
  558.     return (ALLOCSIZE(sizeof(DICTIONARY)));
  559.     case DT_VAR:
  560.     return (ALLOCSIZE(sizeof(DICT_ENTRY)));
  561.     case DT_IOSTREAM:
  562.     return (ALLOCSIZE(sizeof(IOSTREAM)));
  563.     }
  564.     error("Bad block type: %d",hdr->hdr_type);
  565.     return (0);
  566. }
  567.  
  568. /* compact_vector - compact a vector segment */
  569. static void compact_vector(vseg)
  570.   VSEGMENT *vseg;
  571. {
  572.     AUNIT *vdata,*vnext,*vfree;
  573.     VALUE *vp,*nextvp;
  574.     int vsize;
  575.     HDR *hdr;
  576.  
  577.     /* update pointers */
  578.     vdata = vnext = vseg->vs_data;
  579.     vfree = vseg->vs_free;
  580.     while (vdata < vfree) {
  581.     hdr = (HDR *)vdata;
  582.     vsize = getblocksize(hdr);
  583.     if (hdr->hdr_flags & MARK) {
  584.         for (vp = hdr->hdr_chain; vp != NULL; vp = nextvp) {
  585.         nextvp = vp->v.v_chain;
  586.         vp->v.v_hdr = (HDR *)vnext;
  587.         }
  588.         hdr->hdr_chain = NULL;
  589.         vnext += vsize;
  590.     }
  591.     else {
  592.         switch (hdr->hdr_type) {
  593.         case DT_IOSTREAM:
  594.         ((IOSTREAM *)hdr)->ios_dispatch->iod_close(
  595.             ((IOSTREAM *)hdr)->ios_data);
  596.         break;
  597.         }
  598.     }
  599.     vdata += vsize;
  600.     }
  601.  
  602.     /* compact free space */
  603.     vdata = vnext = vseg->vs_data;
  604.     vfree = vseg->vs_free;
  605.     while (vdata < vfree) {
  606.     hdr = (HDR *)vdata;
  607.     vsize = getblocksize(hdr);
  608.     if (hdr->hdr_flags & MARK) {
  609.         hdr->hdr_flags &= ~MARK;
  610.         if (vdata == vnext) {
  611.         vdata += vsize;
  612.         vnext += vsize;
  613.         }
  614.         else
  615.         while (--vsize >= 0)
  616.             *vnext++ = *vdata++;
  617.     }
  618.     else
  619.         vdata += vsize;
  620.     }
  621.     vseg->vs_free = vnext;
  622. }
  623.